package org.bhavani.alg;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.ListIterator;

class SimpleFileReader extends Thread {
	private String fileName;
	private LinkedList<String> wordList;
	
	public SimpleFileReader(String file) {
		fileName = file;
		/* Ideally I would use data structure that is like set but allows duplicates */
		wordList = new LinkedList<String>();
	}

	public LinkedList<String> getWordList() {
		return wordList;
	}
	
	@Override
	public void run() {
		try {
			BufferedReader in = new BufferedReader(new FileReader(fileName));
			String s;			
			System.out.println("Reading file " + fileName);
			while ((s = in.readLine()) != null) {
				wordList.add(s);
			}
			Collections.sort(wordList);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

public class DistributedMerge {
	public static LinkedList<String> merge(LinkedList<String> list1, LinkedList<String> list2) {
		LinkedList<String> mergedList = new LinkedList<String>();
		String s1 = list1.peek();
		String s2 = list2.peek();
		while (list1.isEmpty() == false && list2.isEmpty() == false) {
			if (s1.compareTo(s2) < 0) {
				mergedList.add(s1);
				list1.remove();
				s1 = list1.peek();
			} else {
				mergedList.add(s2);
				list2.remove();
				s2 = list2.peek();
			}
		}
		
		if (list1.isEmpty() == false) {
			mergedList.addAll(list1);
		}
		
		if (list2.isEmpty() == false) {
			mergedList.addAll(list2);
		}
		
		return mergedList;
	}
	
	public static void print(LinkedList<String> list) {
		ListIterator<String> itr = list.listIterator();
		while (itr.hasNext()) {
			String s = itr.next();
			System.out.println(s);
		}
	}
	
	public static void main(String args[]) {
		SimpleFileReader[] readers = new SimpleFileReader[4];
		for (int i = 1; i <= readers.length; i++) {
			String fileName = "list" + i + ".txt";
			readers[i-1] = new SimpleFileReader(fileName);
			readers[i-1].start();
		}
		
		LinkedList<String> mergedList = new LinkedList<String>();
		/* wait for all the threads finish */
		for (int i = 0; i < readers.length; i++) {
			try {
				readers[i].join();
				System.out.println("Thread " + i + " finished reading");
				mergedList = merge(mergedList, readers[i].getWordList());
			} catch (InterruptedException e) {				
				e.printStackTrace();
				return;
			}
		}
		
		print(mergedList);
		
	}

}
